package com.gaogzhen.datastructure.graph.directed;

import edu.princeton.cs.algs4.Digraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

/**
 *  顶点对的可达性
 * @author gaogzhen
 */
public class TransitiveClosure {

    /**
     * 顶点v起点的可达有向图
     */
    private DirectedDFS[] tc;

    /**
     * 计算有向图G的传递闭包
     * @param G 给定有向图
     */
    public TransitiveClosure(Digraph G) {
        tc = new DirectedDFS[G.V()];
        for (int v = 0; v < G.V(); v++) {
            tc[v] = new DirectedDFS(G, v);
        }
    }

    /**
     * 顶点w是从v可达的吗
     * @param  v 给定顶点
     * @param  w 目标顶点
     * @return {@code true} 顶点w从顶点v可达,{@code false} 否则
     * @throws IllegalArgumentException unless {@code 0 <= v < V}
     * @throws IllegalArgumentException unless {@code 0 <= w < V}
     */
    public boolean reachable(int v, int w) {
        validateVertex(v);
        validateVertex(w);
        return tc[v].marked(w);
    }

    /**
     * 校验顶点v
     * @param v 顶点v
     */
    private void validateVertex(int v) {
        int V = tc.length;
        if (v < 0 || v >= V) {
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
        }
    }
}